package coursera.assignments;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class SCCNew {

	public static Map<String, Vertex> vertexes = new TreeMap<String, Vertex>(
			Collections.reverseOrder());

	public class Vertex implements Comparable<Vertex> {
		public Vertex() {
		}

		public Vertex(String label) {
			this.label = label;
		}

		String label;

		List<Vertex> in = new ArrayList<Vertex>();
		List<Vertex> out = new ArrayList<Vertex>();
		Vertex leader = null;

		boolean visited = false;
		Integer finishingTime = null;

		@Override
		public int compareTo(Vertex a) {
			return label.compareTo(a.label);
		}

		@Override
		public boolean equals(Object other) {
			return this.label.equals(((Vertex) (other)).label);
		}

		@Override
		public int hashCode() {
			return label.hashCode();
		}
	}


	public void addVertex(String label) {
		if (vertexes.get(label) == null) {
			Vertex vertex = new Vertex();
			vertex.label = label;
			vertexes.put(label, vertex);
		}
	}

	public void addEdge(String source, String destination, int weight,
			String label) {
		(vertexes.get(source)).out.add(vertexes.get(destination));
		(vertexes.get(destination)).in.add(vertexes.get(source));
	}

	static void traverseGraphDFS(Vertex root, boolean reverse) {
		root.visited = true;
		sizeOfCurrentSCC++;
		root.leader = global_s;
		if (reverse) {
			Collections.sort(root.in);
			for (Vertex ver : root.in) {
				if (!ver.visited) {
					traverseGraphDFS(ver, reverse);
				}
			}
			global_t++;
			root.finishingTime = global_t;
		} else {
			Collections.sort(root.out);
			for (Vertex ver : root.out) {
				if (!ver.visited) {
					traverseGraphDFS(ver, reverse);
				}
			}
		}

	}

	private static int global_t = 0;
	private static Vertex global_s = null;
	private static int sizeOfCurrentSCC = 0;
	private static List<Integer> THE_BIG_FINAL_LIST = new ArrayList<Integer>();

	static void traverseGraphDFS_SCC(boolean reverse) {
		if (reverse) {
			for (Map.Entry<String, Vertex> entry : vertexes.entrySet()) {
				Vertex vertex = entry.getValue();
				if (!vertex.visited) {
					global_s = vertex;
					traverseGraphDFS(vertex, reverse);
				}
			}
		} else {
			for (int i = 0; i < vertexes.size(); i++) {
				sizeOfCurrentSCC = 0;
				Vertex temp = null;
				int maxFinishingTime = Integer.MIN_VALUE;
				for (Map.Entry<String, Vertex> entry : vertexes.entrySet()) {
					if (!entry.getValue().visited
							&& entry.getValue().finishingTime > maxFinishingTime) {
						maxFinishingTime = entry.getValue().finishingTime;
						temp = entry.getValue();
					}
				}
				if (temp != null) {
					traverseGraphDFS(temp, false);
					if (!THE_BIG_FINAL_LIST.contains(sizeOfCurrentSCC)) {
						THE_BIG_FINAL_LIST.add(sizeOfCurrentSCC);
					}
				}
			}
		}
	}
	
	/**
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {
		SCC myGraph = new SCC();

		FileReader fr = null;
		BufferedReader br = null;
		try {
			fr = new FileReader("SCCCourse.txt");
			br = new BufferedReader(fr);
			String line;
			while ((line = br.readLine()) != null) {
				String[] split = line.trim().split("(\\s)+");
				myGraph.addVertex(split[0]);
				myGraph.addVertex(split[1]);
				myGraph.addEdge(split[0], split[1], 0, split[0] + split[1]);
			}
		} catch (FileNotFoundException e1) {
			e1.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			br.close();
		}
		traverseGraphDFS_SCC(true);
		for (Map.Entry<String, Vertex> entry : vertexes.entrySet()) {
			entry.getValue().visited = false;
			 System.out.println(entry.getValue().label
			 +"  "+entry.getValue().finishingTime );
		}
		traverseGraphDFS_SCC(false);
		for (int value : THE_BIG_FINAL_LIST) {
			System.out.println(value);
		}
	}

}